Randomness is a basic and well-known tool in many disciplines of science and technology and finds application in fields such as communications, data security, access-control, and processes based on chaos theory.
In some systems, such as frequency hopping based systems, there is a need for identical and simultaneous randomness at different remote locations. Furthermore, a random result employed at the remote locations is preferably confidential and unknown to an unauthorized party. Examples include
(i) secret key data encryption methods, in which both communicating parties need to have the same secret key, which is typically a random key;
(ii) remote access control, in which a distant operator needs to have the same password as that installed in a ‘machine’ to be accessed—this password is preferably a random password; and
(iii) chaos processes which are executed remotely.
Encryption, in particular, is a necessary tool in electronic communications, wherein data of highly sensitive content is propagated through public networks. An ideal data security system using encryption technology as the principle tool should be able to provide the following three features:
1) provide identification and authentication of the data source and destination,
2) prevent unauthorized access to the data, and
3) protect the data from unauthorized tampering.
Generally speaking, encryption involves turning a meaningful series of data into a meaningless and apparently random sequence. Recovery of the original meaningful sequence is only possible with certain additional information. Certain encryption systems allow a receiver of data to determine that the data has been altered following encryption. Likewise, certain ways of using encryption keys allows for electronic signature of the data, so that the receiver of the data is able to be sure who the sender is, and suitable use of the electronic signature allows both parties to be sure of the other party.
The vast majority of encryption systems include two components, an algorithm, or encryption method, and a key, which, generally speaking, contains values to be used at various steps in the algorithm.
For the most part, the algorithms used in encryption systems are known. The exceptions are in certain government applications, and generally it is very inadvisable for an encryption system to rely on the secrecy of the algorithm. Thus, the security of most encryption systems lies with the secrecy of the key.
Generally speaking, encryption methods may be classified into groups as follows:
symmetric (secret key) encryption,—as opposed to asymmetric (public key) encryption,
random (one time pad) encryption,—as opposed to algorithmic encryption,
block enciphering, as opposed to stream enciphering, etc.
However, in each case, in the broad sense outlined above, in order to obtain a closed solution having all features of data security, there is the need to share secret information in order for the system to work
Approaches for breaking into encryption systems to allow unauthorized access to the data, may be grouped into four. They are:                1. Reverse engineering        2. Cryptanalysis and mathematical methods,        3. Tape and retransmit,        4. Exploitation of human weakness.        
The above approaches are often used in combination and in general, secure encryption has to be based on the assumption that any key, after being used for a certain amount of time, will tend to become known. Secure communication thus requires frequent changes to the key. In particular, as available computing power is growing, key lifetime is becoming shorter and shorter.
The process of regularly changing keys is known as key management, and key management is thus becoming a more and more important part of encryption and secure communication.
When using symmetric encryption systems, the exact same key is needed at both parties and thus key management involves the transfer of the key from one party to another.
When using asymmetric systems, key changeover is simpler. If one party changes his key, then internally he changes his private key, which is needed for reading any messages. He then only has to transmit the public key, which does not need to be kept secret. The public key is needed for encryption but is completely useless for decryption of the message. However, even in the case of asymmetric systems, there remains the issue of changeover occurrence. If one party starts to use the key before the other, then there will be a short period of unintelligible conversation. Furthermore, when one party receives a new key, he needs to be sure that the key he has received indeed comes from the other party and not from an eavesdropper. Generally, asymmetric systems use a system of mutually exchanging keys so that they are able to rely on each other. Nevertheless, difficulties remain, for example where authorized parties lose synchronization at the crucial moment of key exchange.
One approach in key management involves the use of a trusted third party, a so-called certificate authority. The certificate authority manages key changes for all the users. However, the use of a certificate authority does not actually solve any of the key management problems as such, it simply moves them all on one stage.
Thus, modern secure communication essentially is a question of key management, and the key management issue may be summed up by the following statements:
Communication security relies on secret information (the key).
A secure communication system may be regarded as a chain, and the level of security provided is that of the weakest link in that chain.
The more a key has been used the less secret it is.
Computing power increases at a steady rate, and as that power increases, so does the lifetime of the key decrease, thus necessitating more and more frequent changing of the key or the use of computationally more complex keys.
The regular exchange of keys necessitated by the above must be carried out without giving any information away to eavesdroppers.
Current key management systems include two major categories, the master key category and the public key category. The master key category preferably utilizes a key hierarchy in which heavy master keys are used for secure transfer of session keys, which session keys are used for the encryption of the bulk of the communicated data. The approach fails to solve in depth any of the problems discussed above since weaknesses associated with the lower level session keys are simply transferred to the higher level master keys. Whilst it is true that it is harder for an eavesdropper to deal with the higher level keys the approach does not provide any conceptual increase in security level since the higher level keys are not generally changed.
The public key approach to key management is simply to exchange public keys at intervals. In general the public key is a computationally intensive key to generate, and is regarded as being computationally intensive for decryption and thus the keys are not changed regularly. However, it should be borne in mind that the computational effort to break the key is important only to one out of the four methods for breaking the system, and indeed is of no importance at all to the reverse engineering and human weakness approaches or to hacking, in which the eavesdropper attempts to enter a computer system and obtain the keys. Thus, failure to carry out regular key exchange even in public key encryption systems is here regarded as a mistake.
As mentioned above, the public key system relies for the user identification part of the key transfer on a mutual key transfer with each side using his private key to sign the message. The identification step may be carried out with the help of a certificate authority acting as a trusted third party. However, in either case, the computational complexity of generating new keys together with the identification needs, management effort and administration tasks discourage effective key management practice and key exchange using the public key system boils down in practice to using a fixed key.
In order for a key to be secure, it requires an element of unpredictability. For example with the RSA public key, which is the multiple of two large prime numbers, if the prime numbers themselves, from which the key is built are in any way predictable, the RSA key is not secure.
Keys or key systems for encrypted data as described above, preferably rely on random processes for their creation. Authorized parties to a given communication must have compatible keys. However it is preferable to avoid sending keys, both in order to avoid interception, and to make the encryption process itself simpler and faster. The sending of keys is especially risky in the case of symmetric key systems where the key transmitted is the key needed for decrypting the message. Also the sending of keys delays the communication process. Preferably, therefore, the ideal key management system should allow users to produce the same random key independently. If the key is to be generated using a random process, however, then the two parties cannot conventionally generate the same random process separately, because if it can be exactly repeated then it cannot be random. Indeed the ability to reproduce the process defies the definition of randomness, and no process that can be repeated may be truly random.
A particular environment in which encryption is important is the Internet. Increasingly, the Internet is becoming the forum for business and other transactions in which confidentiality is necessary. Generally, over the Internet, most users expect encryption to work substantially transparently, at the very least not to hold up communication. The communication itself takes place over an open channel in which data is passed from one node to another and may actually be stored on intermediate nodes where it can be accessed later by eavesdroppers. An efficient system of key management, which does not slow down communication and also does not leave keys lying around on intermediate Internet nodes, is therefore needed.
Current approaches for providing simultaneous availability of random results may be grouped into two general families of solutions:
(i) generating randomness at one party, and sending it to the other party; and
(ii) using a pseudo random process at both parties, e.g., a PRNG (Pseudo Random Number Generator) which gives the same random bit stream as an output at both ends if fed by the same input seed.
The above approaches are limited because both the key and the seed may be intercepted by an unauthorized party. The latter approach is demonstrated by, for example, U.S. Pat. No. 5,703,948, in which a system and method are described, for transmitting encrypted messages between two parties, wherein the encrypting key is generated by two state machines, one at each party, which state machines are both identically initialized. The state machines dynamically produce changing keys, by using, each time, some randomly selected bits of a message as seeds for the next key. The machines at both ends are synchronized by using the same seed bits each time, thereby producing the same keys at both ends. Apparently, the parties have to worry about the confidentiality of the initial seed and of the dynamically changing seeds during the course of the message.
There is thus required a system of randomly setting encryption keys identically at remote locations wherein the random data for setting the keys, and certainly the keys themselves, are not available to an eavesdropper. It would further be advantageous if such a system were to include the other listed requirements of an encryption system, namely allowing for mutual identification between users and a way of recognizing whether data has been interfered with en route. A preferred system should also include a way of checking on synchronization and a way of restoring synchronization in the event of synchronization loss.
In the context of mutual identification and maintenance of synchronization, reference is made to the Byzantine agreement problem.
Two remote armies, A and B, approach from different directions to besiege a powerful city. Neither army alone is powerful enough to overcome the city and should it appear on the battlefield alone it will be destroyed. Only if both armies appear simultaneously and from opposite directions is there any chance of success.
The overall commander, located with army A, has to co-ordinate an attack, but has at his disposal dispatch riders as his only means of communication.
The overall commander thus sends a message to the commander of Army B, by dispatch rider, which conveys time of and directions for the intended attack. However, having sent the message by a courier, the commander of army A cannot be certain that the message has reached its destination, (and if it has, that it has not been tampered with on the way). Thus, logic dictates that he will not attack, due to his instinct for self-preservation.
Having received the message, the commander of Army B is faced with the same problem, he cannot be certain that the content of the message is real and that it indeed comes from his ally. It could be a false message sent by the enemy and intended to lure him to his destruction. Furthermore, he knows that commander A has an instinct for self-preservation which is no less real than his own. Thus he must assume that A will not attack and hence he too, does not attack.
Furthermore, he knows that his ally, the commander of army A, will be faced with the same dilemma when receiving his acknowledgement and is unlikely to launch an attack on the basis of this information. Army B, in any case sends back to Army A an acknowledgment message, of the time of and directions for of the attack. Army A receives the acknowledgement but also cannot be sure that the acknowledgement is genuine and has not been sent by the enemy to lure them to their destruction. Furthermore, A knows of B's instinct for self-preservation. Bearing this in mind, army A must assume that army B will not attack. The situation is not improved however many further rounds of acknowledgement or confirmation are carried out. That is to say, having sent the acknowledgment message, both army A and army B keep facing the same dilemma of not being able to assume that the other will attack and, as a result, an attack will never be launched.
The “Byzantine Agreement Problem”, is a logical dilemma that is relevant when translated into modern communications, especially when considering for example, open communication modes such as the Internet, which are exposed to hackers, imposters etc. and to errors and breaks in communications.
The issues that this logical dilemma presents, and need to be solved are (i) synchronization; (ii) simultaneity; (iii) identification; and (iv) authentication.
At the basis of the problem lies the fact that at any given step, one party knows less than the other, and there is a lag between the knowledge of the parties (about the situation of one party in regard to the other party, and in their mutual understanding)
The Byzantine agreement problem thus raises the following issues, synchronization, simultaneity, identification and authentication. The root of the problem is that at any given leg of the communication procedure, one party leads and one party lags, even if by nanoseconds, thus leading to scope for dispute and for impersonation.
The depth of the problem may be demonstrated by illustrating two approaches that have been used in attempted solutions in the past.
1) Clock timing synchronization. Each party has an identically set clock. A parameter changes at predetermined clock settings. Unfortunately the two clocks cannot be set so accurately with respect to one another that no dispute occurs at any time. Even a difference of nanoseconds can lead to dispute over some of the data.
2) Synchronization by announcement. A parameter change is made upon receipt of a predetermined announcement. Unfortunately, this approach begs the very essence of the Byzantine agreement problem, since I do not know whether the other side has received the announcement, or whether it originates from a legitimate source at all.
There is thus a widely recognized need for, and it would be highly advantageous to have, a simple and practical way to produce identical ongoing randomness at separate and remote locations, that is confidential in nature and which enables a mode of communication, synchronization or authentication between two parties that is not vulnerable to the logical dilemmas of the Byzantine agreement problem, and which may provide a comprehensive solution to secure key management.